package com.waiting.leetcode;

/**
 * @Description
 * @Author bjweitingting
 * @Date 2019/3/27
 **/
public class NumberOfLongestIncreasingSubsequence673 {
    public static void main(String[] args) {

    }

    public int findNumberOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] lengthDp = new int[nums.length];
        int[] countDp = new int[nums.length];
        lengthDp[0] = 1;
        countDp[0] = 1;
        int maxLength = lengthDp[0];
        int count = countDp[0];
        for (int i = 1; i < nums.length; i++) {
            lengthDp[i] = 1;
            countDp[i] = 1;
            for (int k = 0; k < i; k++) {
                if (nums[i] > nums[k]) {
                    if (lengthDp[k] + 1 > lengthDp[i]) {
                        lengthDp[i] = lengthDp[k] + 1;
                        countDp[i] = countDp[k];
                    } else if (lengthDp[k] + 1 == lengthDp[i]) {
                        countDp[i] += countDp[k];
                    }
                }
            }
            if (lengthDp[i] > maxLength) {
                count = countDp[i];
                maxLength = lengthDp[i];
            } else if (lengthDp[i] == maxLength) {
                count += countDp[i];
            }
        }
        return count;
    }
}
